# 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
#
#  示例:
#
#  输入:
# [
#   ["1","0","1","0","0"],
#   ["1","0","1","1","1"],
#   ["1","1","1","1","1"],
#   ["1","0","0","1","0"]
# ]
# 输出: 6
#  Related Topics 栈 数组 哈希表 动态规划
#  👍 576 👎 0

# todo
# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0
        m = len(matrix)
        n = len(matrix[0])

        max_area = 0

        hs = [0 for _ in range(0, n)]
        for i in range(0, m):
            for j in range(0, n):
                if i == 0:
                    hs[j] = 0 if matrix[i][j] == "0" else 1
                else:
                    hs[j] = 0 if matrix[i][j] == "0" else hs[j] + 1

            max_area = max(max_area, self.maxRect(hs[:]))

        return max_area

    def maxRect(self, heights):

        max_area = 0

        stack = []

        n = len(heights)
        for i in range(0, n):

            if len(stack) == 0 or heights[i] > heights[stack[-1]]:
                stack.append(i)
            else:
                top = 0
                while len(stack) > 0 and heights[i] <= heights[stack[-1]]:
                    top = stack[-1]
                    max_area = max(max_area, (i - top) * heights[top])
                    stack.pop()

                heights[top] = heights[i]
                stack.append(top)

        # leetcode submit region end(Prohibit modification and deletion)

        while len(stack) != 0:
            top = stack.pop()
            width = len(heights) if len(stack) == 0 else len(heights) - top

            max_area = max(max_area, width * heights[top])

        return max_area


print(Solution().maximalRectangle([
    ["1", "0", "1", "0", "0"],
    ["1", "0", "1", "1", "1"],
    ["1", "1", "1", "1", "1"],
    ["1", "0", "0", "1", "0"]
]))